package primary.linkedList;

/**
 * @Author Elephas
 * @Date 2022/1/8
 **/
public class IsPalindrome {
    public static void main(String[] args) {
        ListNode test01 = ListNode.ListNode(new int[]{1,2});
        boolean result = isPalindrome(test01);
        return;
    }
    /*
        解法一：将数组后半部分逆序，然后比对,可以考虑写成多个函数，多个过程堆砌有点难看
        官方解答
        整个流程可以分为以下五个步骤：
         找到前半部分链表的尾节点。
         反转后半部分链表。判断是否回文。
         恢复链表。
         返回结果。

     */
    public static boolean isPalindrome(ListNode head){
        ListNode pNode = head;
        // 获取链表长度
        int nodeNums = 0;
        while(pNode != null){
            pNode = pNode.next;
            nodeNums++;
        }

        // 找到后半部分开始节点的位置
        int half = nodeNums%2 == 0? nodeNums/2+1 : nodeNums/2+2;
        pNode = head;

        // 将后半节点用头插法逆序
        ListNode fakeHead = new ListNode(0,null);
        ListNode temp;
        for (int i = 1; i < half; i++) {
            pNode = pNode.next;
        }
        while(pNode != null){
            temp = pNode;
            pNode = pNode.next;
            temp.next = fakeHead.next;
            fakeHead.next = temp;
        }


        // 逐个节点比对
        pNode = head;
        ListNode pNode2 = fakeHead.next;
        while(pNode != null && pNode2 != null){
            if(pNode.val != pNode2.val)
                return false;
            pNode = pNode.next;
            pNode2 = pNode2.next;
        }

        return true;
    }
}
